package com.dmall.graph.floodfill;

import java.util.HashMap;
import java.util.HashSet;

/**
 * @author xiao1.wang
 * @date 2020-06-05 12:26:57
 */
public class Leetcode827V3 {
    private int R, C;
    private int[][] grid;
    private int[][] gridGroup;
    private int[][] dirs = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
    private final HashMap<Integer, Integer> groupCountMap = new HashMap<>();

    public int largestIsland(int[][] grid) {
        R = grid.length;
        C = grid[0].length;

        this.grid = grid;
        boolean allZero = true;
        gridGroup = new int[R][C];
        int max = 0;
        int group = 1;
        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if (grid[i][j] == 1 && gridGroup[i][j] == 0) {
                    allZero = false;
                    int count = dfs(i, j, group);
                    groupCountMap.put(group, count);
                    group++;
                }
            }
        }

        if (allZero) {
            return 1;
        }

        for (int i = 0; i < R; i++) {
            for (int j = 0; j < C; j++) {
                if (grid[i][j] == 0) {
                    max = Math.max(max, dfs(i, j));
                }
            }
        }

        if (max == 0) {
            return R * C;
        }

        return max;
    }

    private int dfs(int x, int y, int group) {
        int res = 1;
        gridGroup[x][y] = group;
        for (int i = 0; i < dirs.length; i++) {
            int nextx = x + dirs[i][0];
            int nexty = y + dirs[i][1];
            if (inArea(nextx, nexty) && gridGroup[nextx][nexty] == 0 && grid[nextx][nexty] == 1) {
                res += dfs(nextx, nexty, group);
            }
        }
        return res;
    }

    private int dfs(int x, int y) {
        int res = 1;
        HashSet<Integer> set = new HashSet<>();
        for (int i = 0; i < dirs.length; i++) {
            int nextx = x + dirs[i][0];
            int nexty = y + dirs[i][1];
            if (inArea(nextx, nexty) && groupCountMap.containsKey(gridGroup[nextx][nexty]) && !set.contains(gridGroup[nextx][nexty])) {
                res += groupCountMap.get(gridGroup[nextx][nexty]);
                set.add(gridGroup[nextx][nexty]);
            }
        }
        return res;
    }

    private boolean inArea(int x, int y) {
        return x >= 0 && x < R && y >= 0 && y < C;
    }

    public static void main(String[] args) {
        int[][] grid = {{1, 0}, {0, 1}};
        // int[][] grid = {{1, 1, 1, 1, 0}, {1, 0, 0, 0, 0}, {0, 0, 0, 1, 1}, {1, 1, 0, 1, 0}, {0, 0, 0, 0, 1}};
        Leetcode827V3 leetcode827 = new Leetcode827V3();
        int res = leetcode827.largestIsland(grid);
        System.out.println(res);
    }
}
